This invention generally relates to systems and methods for designing error-correcting codes used to write and read data on data storage channels. In particular, embodiments of the invention pertain to systems and methods for constructing high-performance concatenated codes for holographic data storage channels.
As demand for digital data storage capacity increases, data storage systems must continue to store and retrieve data accurately, reliably, and quickly. The accuracy, reliability, and throughput of data storage may decrease due to any number of sources for error. For example, noise or interference present in the data storage channel, defects in a data storage medium, and intersymbol interference may result in data read or write errors. Some communication or data storage channels are also subject to errors which are dependent on the particular data symbols being written to or read from the data storage channel. In other words, the statistics, such as the mean and variance, of the noise corrupting the signals corresponding to the data symbols are different or asymmetric. Inevitably, the data stored in data storage systems using such channels is a distorted version of the written data.
Data storage systems often use error-correcting codes to increase data storage accuracy, reliability, and throughput. Error-correcting codes may achieve these improvements by encoding data at a transmitter, often during the data writing process, into a set of data symbols. This encoding process adds redundancy, so that the length of the block of data written to the data storage medium is often longer than the amount of originally transmitted data. Decoding may be performed by employing an efficient decoding algorithm after the data is read from the data storage medium. This decoding algorithm may be implemented on data processing circuitry, such as a field-programmable gate array (FPGA) or application specific integrated circuit (ASIC).
One error-prone data storage system is a holographic data storage system, which uses a holographic disk as its data storage medium and transmits data over a holographic data storage channel. In certain holographic data storage systems, data is arranged in an array, or page, of about a million (or more) bits. The pages may then be organized into chapters, and the chapters may be organized into books. High data storage densities of up to 320 pages per book have been achieved. These pages are stored within the same three-dimensional disk space, with each page offset from the next one by a very small angle (e.g., offset by 0.067 degrees). In addition, in order to achieve high storage densities, the spacing between the books may be minimized (e.g., book spacing of 700 micrometers has been achieved). Further, the holographic data storage channel is often an asymmetric channel.
Due to these and other characteristics of holographic data storage systems, powerful error-correction codes are needed to minimize the system's bit error rate (BER) and/or sector error rate (SER) and maximize the system's coding gain. The BER is the ratio of the number of incorrectly decoded data bits versus the total number of transmitted data bits. Similarly, the SER is the ratio of the number of incorrectly decoded sectors/blocks of data bits versus the total number of transmitted sectors/blocks. Finally, the signal to noise ratio is the ratio of signal power to noise power as data is transmitted on a channel, such as a holographic data storage channel. Because holographic storage channels have strict system requirements, very strong error correction codes are needed that achieve large SNR gains.
One method for achieving higher performance of forward error correction codes without the use of particularly long codes is to use a family of codes known as concatenated codes. For example, FIG. 1 shows system 100 for encoding and decoding user information using a concatenated code. A simple concatenated code is formed from two codes: an (n1, k1) code C1 and an (n2, k2) code C2. More than two codes may be used in other concatenated code implementations. Concatenation of two error correcting codes typically utilizes an inner encoder or decoder and an outer encoder or decoder. The terms “inner” and “outer” refer to the physical location of the encoders/decoders in the transmission system relative to the communication channel. As shown in the example of system 100, inner encoder 104 and inner decoder 108 are positioned closer to channel 106, while outer encoder 102 and outer decoder 110 are positioned outside of inner encoder 104 and inner decoder 108, respectively.
System 100 includes concatenated encoders 102 and 104 where outer encoder 102 has a (n2, k2) code and is coupled to inner encoder 104 of a (n1, k1) code. The output of encoder 104 may be stored on or written to channel 106. The stored data may be received by a receiver comprising concatenated decoders 108 and 110. Inner decoder 108 may decode code (n1, k1), and outer decoder 110 may decode code (n2, k2).
FIG. 1 illustrates the typical encoding process used with concatenated codes. The encoding process typically consists of two steps. First, the binary user information data is parsed into blocks of k2 user information digits each. These k2 bits are then encoded according to the rules for C2 to form an n2-bit codeword. Second, the n2-bit codewords are grouped (and possibly interleaved) and then parsed into blocks of k1 bits. Then, each block of k1 bits is encoded into a codeword in C1, resulting in a string of codewords of C1. These digits may then be transmitted one codeword at a time in succession onto channel 106.
The decoding process is also generally performed in two steps. Decoding is first performed for each C1 codeword as it arrives using a decoding algorithm for the inner code, and then the check digits (or parity bits) are removed. These bits are then decoded using a decoding algorithm for the C2 outer code, resulting in the final corrected user information. Although the example of system 100 shows one-level concatenation, multi-level concatenation may also be used. In multi-level concatenation, several codes are used to form multiple concatenated codes. These codes may then be combined to form an overall concatenated code.
Since the accuracy and reliability of a holographic data storage system suffers when the SNR is low, there is a continuing interest in constructing efficient concatenated codes that will provide significant improvements in SNR when implemented on particular data storage channels.